package validate.sudoku;

import java.util.HashSet;
import java.util.Set;

/**
 * @Time 2019/12/30
 * @author 王光浩
 * @Need 给定一个9*9的数独数据，判断填充的数独数据是否有效。
 * @Thinking 使用暴力法解决问题。
 *           思路：首先判断所有行和所有列是否存在相同的数字，如果存在则返回false，然后判断9个3*3方框中
 *                 是否存在相同的数据，如果存在则返回false，否则返回false。
 *           复杂度分析：时间复杂度O（1），因为给定的数据最大长度是固定的，空间复杂度O（1）
 */
public class MyMethodOne {
    public boolean isValidSudoku(char[][] board) {
    	Set<Character> column=new HashSet<Character>();
    	Set<Character> row=new HashSet<Character>();
    	//判断所有行或列是否存在相同的数字
    	for(int i=0;i<9;i++) {
    		for(int j=0;j<9;j++) {
    			if((board[j][i]!='.' && !column.add(board[j][i])) || (board[i][j]!='.' && !row.add(board[i][j])))
    					return false;
    		}
    		column.clear();
    		row.clear();
    	}
    	
    	//判断每一个3*3宫格中是否存在相同的数字
    	for(int i=0;i<9;i+=3) {
    		for(int j=0;j<9;j+=3) {
    			if(!judge(i,j,board))
    				return false;
    		}
    	}
        return true;
    }
    /**判断一个3*3宫格中是否存在相同的数字*/
    private boolean judge(int x,int y,char[][] board) {
    	Set<Character> sub_board=new HashSet<Character>();
    	for(int i=0;i<3;i++) {
    		for(int j=0;j<3;j++) {
    		   if(board[x+i][y+j]!='.') {
    			   if(!sub_board.add(board[x+i][y+j]))
    				   return false;
    		   }
        	}
    			
    	}
    	return true;
    }
}
